/**
 * 
 */
package edu.cmu.cs211.seamcarving;

import java.util.Iterator;
import java.util.Vector;

/**
 * Class that is used to find the minimum energy vertical seam in an image
 * 
 */
public class SeamFinder {

  public SeamFinder() {

  }

  /**
   * Finds the minimum vertical seam in the cost image. A seam is a connected
   * line through the image.
   * 
   * @param costs The cost of removing each pixel in the image
   * @return A vector the same height as the image where each entry specifies,
   *         for a single row, which column to remove. So, if vector[5] = 3,
   *         then the minimum seam goes through the pixel at row 5 and column 3.
   */
  /*
   * The method findMinSeam consists of 3 steps:
   * 1. build a minCost table using bottom up dynamic programming
   * 2. read off the lowest cost directly from the last row of the table
   * 3. Trace up from the last row of the table, and find the smallest value
   *  of the accessible elements, and insert into the vector seam
   */
  public Vector<Integer> findMinSeam(GrayImage costs) {
	  Vector<Integer> seam = new Vector<Integer>();
	  int rows = costs.getHeight(); //height
	  int cols = costs.getWidth();	//width
	  float[][] minCost = new float[rows][cols];
	  float l, m, r;
	  
	  // build a table of minCost using bottom up dynamic programming
	  for(int i = 0; i < rows; i++)
	  {
		  for(int j = 0; j < cols; j++)
		  {
			 if(i == 0)	// fill up row 0
				 minCost[i][j] = costs.get(i, j);
			 else
			 {
				 m = costs.get(i-1, j);	// set top medium
				 if(j == 0)	// col0
				 {
					 l = Float.MAX_VALUE;
					 r = costs.get(i-1, j+1);
				 }
				 else if(j == cols-1)	//last col
				 {
					 l = costs.get(i-1, j-1);
					 r = Float.MAX_VALUE;
				 }
				 else	// cols in the middle
				 {
					 l = costs.get(i-1, j-1);
					 r = costs.get(i-1, j+1);
				 }
				 // insert into minCost table
				 minCost[i][j] = costs.get(i, j) + Math.min(l, Math.min(m, r));
			 }
		  }
	  }
	  
	  // find the min cost in the last row of the table
	  float min = minCost[rows-1][0];	// the minimum cost
	  int jTracker = 0;	// j index of the smallest value of the previous row
	  for(int j = 1;j <cols; j++)
	  {
		  if(minCost[rows-1][j] < min)
		  {
			  min = minCost[rows-1][j];
			  jTracker = j;
		  }
	  }
	  seam.add(0, jTracker);
	  // walk up the minCost table and insert to 
	  for(int iTracker = rows-2; iTracker>=0; iTracker--)
	  {
		  // find the minimum of left, middle, right
		  float left = (jTracker == 0)?Float.MAX_VALUE:minCost[iTracker][jTracker-1];
		  float right = (jTracker == cols-1)?Float.MAX_VALUE:minCost[iTracker][jTracker+1];
		  float middle = minCost[iTracker][jTracker];
		  float minValue = Math.min(left, Math.min(right, middle));	// find min value of left, middle, right
		  //update jTracker
		  if(minValue == left)
			  jTracker = jTracker-1;
		  else if(minValue == right)
			  jTracker = jTracker+1;
		  //insert into seam
		  seam.add(0, jTracker);
	  }
	  return seam;
  }
}
